The invention relates to pattern matching in a multiprocessor environment.
Pattern matching (also called string matching) finds occurrences of a string (the pattern) in an input stream of characters. Multiple pattern matching finds occurrences of each string in a set of strings (the patterns) in an input stream of characters. For example, the strings “this” and “fox” occur in the input stream “this is a fox and this is not a fox” at positions 0 and 19 for “this” and positions 10 and 32 for “fox”. The sequence of characters that make up the patterns and that occur in the input stream can come from an arbitrary alphabet, including a standardized character set (e.g., ASCII characters) or any other set of identifiable symbols.
Multiple pattern matching can be performed using multiple sets of patterns, where the input stream of characters is checked against all the patterns in one, or more, of the pattern sets. In some cases, each pattern set is independent of all the other pattern sets.
Multiple pattern matching can be used for Intrusion Detection Systems (IDS) and Intrusion Prevention Systems (IPS) in networking applications. The data rates in these systems can be over 1 GByte/sec. In some cases, different sets of patterns are used to check different types of network packets. Some packets are checked against more than one pattern set.
Pattern matching can also be used for virus scanning. The virus signatures are typically longer than the patterns in IDS/IPS rules, but pattern matching can be implemented in a similar manner.
Some important metrics for a pattern matching system are the rate at which it can process the stream of input characters to be searched and the amount of memory needed to store the set of patterns.
Pattern matching can be used for other applications; e.g., “Data Classification” in smart switches inside a Storage Area Network (SAN). Some storage systems virtualize data file storage based on the types of the files to be stored. The file type and content determine where in the SAN the corresponding file is to be stored. Determination of such fields within files in real time can be performed using pattern matching.